#include <pmm.h>
#include <list.h>
#include <string.h>
#include <default_pmm.h>

/*  In the First Fit algorithm, the allocator keeps a list of free blocks
 * (known as the free list). Once receiving a allocation request for memory,
 * it scans along the list for the first block that is large enough to satisfy
 * the request. If the chosen block is significantly larger than requested, it
 * is usually splitted, and the remainder will be added into the list as
 * another free block.
 * 在首次适应算法中，分配器维护一个空闲块列表,（称为空闲列表）。一旦收到内存的分配请求，
 * 它会沿着列表扫描第一个足够大的块以满足请求。如果选中的块比请求的块大得多，通常会将其拆分，
 * 剩余部分将作为另一个空闲块添加到列表中。
 *  Please refer to Page 196~198, Section 8.2 of Yan Wei Min's Chinese book
 * "Data Structure -- C programming language".
*/
// LAB2 EXERCISE 1: YOUR CODE
// you should rewrite functions: `default_init`, `default_init_memmap`,
// `default_alloc_pages`, `default_free_pages`.
// `default_alloc_pages`, `default_free_pages`.你需要重写函数：
/*
 * Details of FFMA
 * (1) Preparation:
 *  In order to implement the First-Fit Memory Allocation (FFMA), we should
 * manage the free memory blocks using a list. The struct `free_area_t` is used
 * for the management of free memory blocks.
 * * 为了实现首次适应内存分配（FFMA），我们应使用一个列表来管理空闲内存块。
 * 结构体 `free_area_t` 用于管理空闲内存块。
 * 
 *  First, you should get familiar with the struct `list` in list.h. Struct
 * `list` is a simple doubly linked list implementation. You should know how to
 * USE `list_init`, `list_add`(`list_add_after`), `list_add_before`, `list_del`,
 * `list_next`, `list_prev`.
 * 首先，你需要熟悉 `list.h` 中的 `list` 结构。结构体 `list` 是一个简单的双向链表实现。
 * 你需要知道如何使用 `list_init`、`list_add`（`list_add_after`）、`list_add_before`、`list_del`、
 *  `list_next`, `list_prev`.
 * 
 *  There's a tricky method that is to transform a general `list` struct to a
 * special struct (such as struct `page`), using the following MACROs: `le2page`
 * (in memlayout.h), (and in future labs: `le2vma` (in vmm.h), `le2proc` (in
 * proc.h), etc).
 * 有一种巧妙的方法是将通用的 `list` 结构转换为特定的结构（例如 `struct page`），
 * 使用以下宏：`le2page`（在 memlayout.h 中），（在未来的实验中：`le2vma`（在 vmm.h 中）、`le2proc`（在 proc.h 中）等）。
 * 
 * (2) `default_init`:
 *  You can reuse the demo `default_init` function to initialize the `free_list`
 * and set `nr_free` to 0. `free_list` is used to record the free memory blocks.
 * `nr_free` is the total number of the free memory blocks.
 * 你可以重用示例 `default_init` 函数来初始化 `free_list`,并将 `nr_free` 设置为 0。
 * `free_list` 用于记录空闲内存块。`nr_free` 是空闲内存块的总数。
 * 
 * (3) `default_init_memmap`:
 *  CALL GRAPH: `kern_init` --> `pmm_init` --> `page_init` --> `init_memmap` -->
 * `pmm_manager` --> `init_memmap`.
 *  This function is used to initialize a free block (with parameter `addr_base`,
 * `page_number`). In order to initialize a free block, firstly, you should
 * initialize each page (defined in memlayout.h) in this free block. This
 * procedure includes:
 * 此函数用于初始化一个空闲块（带参数 `addr_base`、`page_number`）。
 * 为了初始化一个空闲块，首先，你需要初始化此空闲块中的每一页（在 memlayout.h 中定义）。该过程包括：
 * 
 *  - Setting the bit `PG_property` of `p->flags`, which means this page is
 * valid. P.S. In function `pmm_init` (in pmm.c), the bit `PG_reserved` of
 * `p->flags` is already set.
 * 设置 `p->flags` 的 `PG_property` 位，表示该页有效。注：在 `pmm_init` 函数中（在 pmm.c 中），
 * `p->flags` 的 `PG_reserved` 位已经设置。
 * 
 *  - If this page is free and is not the first page of a free block,
 * `p->property` should be set to 0.
 * 如果该页是空闲的且不是空闲块的第一页，则应将 `p->property` 设置为 0。
 * 
 *  - If this page is free and is the first page of a free block, `p->property`
 * should be set to be the total number of pages in the block.
 * 如果该页是空闲的并且是空闲块的第一页，则应将 `p->property` 设置为该块中的总页数。
 * 
 *  - `p->ref` should be 0, because now `p` is free and has no reference.
 *  After that, We can use `p->page_link` to link this page into `free_list`.
 * `p->ref` 应设置为 0，因为现在 `p` 是空闲的，没有引用。
 * 之后，我们可以使用 `p->page_link` 将此页链接到 `free_list` 中。
 * 
 * (e.g.: `list_add_before(&free_list, &(p->page_link));` )
 *  Finally, we should update the sum of the free memory blocks: `nr_free += n`.
 * （例如：`list_add_before(&free_list, &(p->page_link));`）
 *  Finally, we should update the sum of the free memory blocks: `nr_free += n`.
 * 最后，我们应更新空闲内存块的总数：`nr_free += n`。
 * 
 * (4) `default_alloc_pages`:
 *  Search for the first free block (block size >= n) in the free list and reszie
 * the block found, returning the address of this block as the address required by
 * `malloc`.
 * 在空闲列表中搜索第一个空闲块（块大小 >= n），并调整找到的块的大小，返回该块的地址作为 `malloc` 所需的地址。
 * 
 *  (4.1)
 *      So you should search the free list like this:
 *          list_entry_t le = &free_list;
 *          while((le=list_next(le)) != &free_list) {
 *          ...
 *      (4.1.1)
 *          In the while loop, get the struct `page` and check if `p->property`
 *      (recording the num of free pages in this block) >= n.
 * 在 while 循环中，获取 `struct page` 并检查 `p->property`
 *      （记录该块中空闲页的数量）是否 >= n。
 * 
 *              struct Page *p = le2page(le, page_link);
 *              if(p->property >= n){ ...
 *      (4.1.2)
 *          If we find this `p`, it means we've found a free block with its size
 *      >= n, whose first `n` pages can be malloced. Some flag bits of this page
 *      should be set as the following: `PG_reserved = 1`, `PG_property = 0`.
 *      Then, unlink the pages from `free_list`.
 * 如果我们找到这个 `p`，这意味着我们找到了一个大小>= n 的空闲块，其前 `n` 页可以分配。此页面的一些标志位应设置如下：
 * `PG_reserved = 1`，`PG_property = 0`。然后，从 `free_list` 中移除这些页。
 *          (4.1.2.1)
 *              If `p->property > n`, we should re-calculate number of the rest
 *          pages of this free block. (e.g.: `le2page(le,page_link))->property
 *          = p->property - n;`)
 *          (4.1.3)
 *              Re-caluclate `nr_free` (number of the the rest of all free block).
 *          (4.1.4)
 *              return `p`.
 *      (4.2)
 *          If we can not find a free block with its size >=n, then return NULL.
 * (5) `default_free_pages`:
 *  re-link the pages into the free list, and may merge small free blocks into
 * the big ones.
 *  (5.1)
 *      According to the base address of the withdrawed blocks, search the free
 *  list for its correct position (with address from low to high), and insert
 *  the pages. (May use `list_next`, `le2page`, `list_add_before`)
 *  (5.2)
 *      Reset the fields of the pages, such as `p->ref` and `p->flags` (PageProperty)
 *  (5.3)
 *      Try to merge blocks at lower or higher addresses. Notice: This should
 *  change some pages' `p->property` correctly.
 */
free_area_t free_area;

#define free_list (free_area.free_list)
#define nr_free (free_area.nr_free)

//free_list` 用于记录空闲内存块,nr_free` 是空闲内存块的总数。
//用default_init函数来初始化 `free_list`,并将 `nr_free` 设置为 0。
static void
default_init(void) {
    list_init(&free_list);
    nr_free = 0;
}

//用于初始化一段连续的物理页，并将它们加入到空闲内存管理系统中.
//struct Page *base：指向要初始化的页块的起始地址。size_t n：要初始化的页的数量。
static void
default_init_memmap(struct Page *base, size_t n) {
    assert(n > 0);// 确保请求的页数大于零
    struct Page *p = base;// 指向当前初始化的页
    // 遍历每一页，设置其状态
    for (; p != base + n; p ++) {
        assert(PageReserved(p));//检查每个页是否被标记为“保留”。若没有被保留，函数将抛出错误。
        p->flags = p->property = 0;//将页的 flags 和 property 字段设置为 0，表示该页未分配、未使用。
        set_page_ref(p, 0);//将页的引用计数设置为 0，表明没有任何引用指向此页。
    }
    // 设置第一个页的 property 为块的总数
    base->property = n;
    SetPageProperty(base);// 设置当前页的有效标志
    nr_free += n;// 更新空闲页计数
    list_add_before(&free_list, &(base->page_link));// 将该块添加到空闲列表中
}

//用于分配指定数量的连续物理页。该函数实现了首次适应内存分配算法。
static struct Page *
default_alloc_pages(size_t n) {
    assert(n > 0);// 确保请求的页数大于零
    if (n > nr_free) {// 检查请求的页数是否超过空闲页数
        return NULL;
    }
    struct Page *page = NULL;// 初始化分配的页指针
    list_entry_t *le = &free_list;// 初始化链表迭代器
    // 遍历空闲列表，寻找第一个满足条件的块
    while ((le = list_next(le)) != &free_list) {
        struct Page *p = le2page(le, page_link);// 将链表节点转换为 Page 结构体
        if (p->property >= n) {// 检查当前块的页数是否满足请求
            page = p;// 找到合适的块
            break;// 退出循环
        }
    }
    if (page != NULL) {// 如果找到合适的块
        //list_del(&(page->page_link));// 从空闲列表中删除该块
        if (page->property > n) {
            struct Page *p = page + n;// 指向剩余的页
            p->property = page->property - n;// 更新剩余块的页数
            SetPageProperty(p);
            list_add_after(&(page->page_link), &(p->page_link));// 将剩余块添加回空闲列表
    }
        list_del(&(page->page_link));
        nr_free -= n;// 减少空闲页的计数
        ClearPageProperty(page);// 清除已分配页的属性
    }
    return page;// 返回分配的页块
}

static void
default_free_pages(struct Page *base, size_t n) {
    assert(n > 0);// 确保请求释放的页数大于零
    struct Page *p = base;
    // 遍历释放的页，检查状态并重置
    for (; p != base + n; p ++) {
        assert(!PageReserved(p) && !PageProperty(p));// 确保页没有被保留并且没有属性
        p->flags = 0;// 清除 flags 字段
        set_page_ref(p, 0);// 清除引用计数
    }
    // 设置基页的属性为释放的页数
    base->property = n;
    SetPageProperty(base);// 设置页的有效标志
    // 遍历空闲列表，检查是否需要合并
    list_entry_t *le = list_next(&free_list);
    while (le != &free_list) {
        p = le2page(le, page_link);
        le = list_next(le);
        // 如果当前页块与释放的页块相邻，合并
        if (base + base->property == p) {
            base->property += p->property;// 合并当前页块
            ClearPageProperty(p);// 清除合并页的属性
            list_del(&(p->page_link));// 从空闲列表中删除合并页
        }
        else if (p + p->property == base) {
            p->property += base->property;// 合并前一个页块
            ClearPageProperty(base);// 清除当前页的属性
            base = p;// 更新 base 指针
            list_del(&(p->page_link));// 从空闲列表中删除当前页
        }
    }
    nr_free += n;// 更新空闲页的计数
    le = list_next(&free_list);
    while (le != &free_list)
    {
        p = le2page(le, page_link);
        if (base + base->property <= p)
        {
            assert(base + base->property != p);
            break;
        }
        le = list_next(le);    
    }
    
    list_add_before(le, &(base->page_link));// 将释放的页块添加到空闲列表中
}

//用于返回当前系统中可用的空闲页的数量。
static size_t
default_nr_free_pages(void) {
    return nr_free;// 返回当前空闲页的数量
}

//basic_check 函数用于测试内存分配和释放的基本功能，
//确保在不同情况下内存管理系统的正确性，包括分配、释放、合并和引用计数等操作。
static void
basic_check(void) {
    struct Page *p0, *p1, *p2;
    p0 = p1 = p2 = NULL;
    // 分配三个页面
    assert((p0 = alloc_page()) != NULL);
    assert((p1 = alloc_page()) != NULL);
    assert((p2 = alloc_page()) != NULL);
     // 确保所有分配的页面是不同的
    assert(p0 != p1 && p0 != p2 && p1 != p2);
    // 确保页面的引用计数为 0
    assert(page_ref(p0) == 0 && page_ref(p1) == 0 && page_ref(p2) == 0);
    // 确保页面地址在合法范围内
    assert(page2pa(p0) < npage * PGSIZE);
    assert(page2pa(p1) < npage * PGSIZE);
    assert(page2pa(p2) < npage * PGSIZE);
    // 保存当前的空闲页面链表和数量
    list_entry_t free_list_store = free_list;
    list_init(&free_list);// 初始化空闲列表
    assert(list_empty(&free_list));// 确保空闲列表为空

    unsigned int nr_free_store = nr_free;// 保存当前空闲页数量
    nr_free = 0;// 将空闲页数量设为 0
    // 请求分配页面，但当前没有空闲页面
    assert(alloc_page() == NULL);
    // 释放之前分配的页面
    free_page(p0);
    free_page(p1);
    free_page(p2);
    assert(nr_free == 3);// 确保释放后空闲页数量为 3
    // 再次分配三个页面
    assert((p0 = alloc_page()) != NULL);
    assert((p1 = alloc_page()) != NULL);
    assert((p2 = alloc_page()) != NULL);
    // 测试空闲页面是否不足
    assert(alloc_page() == NULL);
    // 释放 p0，并检查空闲列表
    free_page(p0);
    assert(!list_empty(&free_list));// 确保空闲列表不为空

    struct Page *p;
    // 重新分配 p0，确保取回的是相同的页面
    assert((p = alloc_page()) == p0);
    assert(alloc_page() == NULL);// 确保没有更多的页面可分配

    assert(nr_free == 0);// 确保当前空闲页面数量为 0
    // 恢复之前的空闲页面链表和数量
    free_list = free_list_store;
    nr_free = nr_free_store;
    // 释放最后的页面
    free_page(p);
    free_page(p1);
    free_page(p2);
}

// LAB2: below code is used to check the first fit allocation algorithm (your EXERCISE 1) 
// NOTICE: You SHOULD NOT CHANGE basic_check, default_check functions!
static void
default_check(void) {
    int count = 0, total = 0;
    list_entry_t *le = &free_list;
    // 遍历空闲列表，计算空闲页面的数量和总属性值
    while ((le = list_next(le)) != &free_list) {
        struct Page *p = le2page(le, page_link);
        assert(PageProperty(p));// 确保每个页面的属性是有效的
        count ++, total += p->property;// 累加页面属性
    }
    // 确保总属性值与空闲页面数量匹配
    assert(total == nr_free_pages());
    // 调用 basic_check 以验证基本的内存管理功能
    basic_check();
    // 分配 5 个页面
    struct Page *p0 = alloc_pages(5), *p1, *p2;
    assert(p0 != NULL);// 确保成功分配
    assert(!PageProperty(p0));// 确保分配的页面不带属性
     // 初始化并检查空闲列表
    list_entry_t free_list_store = free_list;
    list_init(&free_list);
    assert(list_empty(&free_list));// 确保空闲列表为空
    assert(alloc_page() == NULL);// 确保没有页面可分配

    unsigned int nr_free_store = nr_free;// 保存当前空闲页数
    nr_free = 0;// 将空闲页数设为 0
    // 释放 3 个页面并确保分配页面时没有足够的空闲页
    free_pages(p0 + 2, 3);
    assert(alloc_pages(4) == NULL);// 确保无法分配 4 个页面
    assert(PageProperty(p0 + 2) && p0[2].property == 3);// 检查页面属性
    assert((p1 = alloc_pages(3)) != NULL);// 再次分配 3 个页面
    assert(alloc_page() == NULL);// 确保没有页面可分配
    assert(p0 + 2 == p1);// 确保分配的页面是释放的页面

    p2 = p0 + 1;// 设置 p2 为 p0 的下一个页面
    free_page(p0);// 释放 p0 页面
    free_pages(p1, 3);// 释放 p1 指向的页面
    assert(PageProperty(p0) && p0->property == 1);// 检查 p0 属性
    assert(PageProperty(p1) && p1->property == 3);// 检查 p1 属性
    // 确保重分配的页面是之前释放的页面
    assert((p0 = alloc_page()) == p2 - 1);
    free_page(p0);// 释放分配的页面
    assert((p0 = alloc_pages(2)) == p2 + 1);// 分配 2 个页面并检查
    // 释放页面并检查空闲状态
    free_pages(p0, 2);
    free_page(p2);
    // 再次分配 5 个页面
    assert((p0 = alloc_pages(5)) != NULL);
    assert(alloc_page() == NULL);// 确保没有额外页面可分配

    assert(nr_free == 0);// 确保空闲页数为 0
    nr_free = nr_free_store;// 恢复空闲页数
    // 恢复空闲列表状态
    free_list = free_list_store;
    free_pages(p0, 5);// 释放所有分配的页面
    // 验证空闲列表的一致性
    le = &free_list;
    while ((le = list_next(le)) != &free_list) {
        struct Page *p = le2page(le, page_link);
        count --, total -= p->property;
    }
    assert(count == 0);// 确保所有页面都已处理
    assert(total == 0);// 确保总属性值为 0
}

const struct pmm_manager default_pmm_manager = {
    .name = "default_pmm_manager",
    .init = default_init,
    .init_memmap = default_init_memmap,
    .alloc_pages = default_alloc_pages,
    .free_pages = default_free_pages,
    .nr_free_pages = default_nr_free_pages,
    .check = default_check,
};

